import java.io.*;
import java.util.*;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    static int[] in = new int[5001];
    static int[] out = new int[5001];
    static int[] num = new int[5001];
    static ArrayList<Integer>[] path = new ArrayList[5001];
    public static void main(String[] args) throws IOException {
        PrintWriter p = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        int n = (int)sc.nval;
        sc.nextToken();
        int m = (int)sc.nval;
        for(int i = 0; i <= n; i++){
            path[i] = new ArrayList<>();
        }
        for(int i = 0; i < m; i++){
            sc.nextToken();
            int B = (int) sc.nval;
            sc.nextToken();
            int A = (int) sc.nval;
            //b指向a
            path[B].add(A);
            in[A]++;
            out[B]++;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        List<Integer> l = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(in[i] == 0){
                num[i] = 1;
                queue.add(i);
            }
            if(out[i] == 0){
                l.add(i);
            }
        }
        while(!queue.isEmpty()){
            int ret = queue.poll();
            List<Integer> child = path[ret];
            for(int i : child){
                num[i] = (num[i] + num[ret]) % 80112002;
                in[i]--;
                if(in[i] == 0){
                    queue.add(i);
                }
            }
        }
        int ans = 0;
        for(int i : l){
            ans = (num[i] + ans) % 80112002;
        }
        System.out.println(ans);
    }
}